//
// Created by Senhai Xu on 2025/3/7.
//
#include <iostream>
#include <queue>
#include <vector>
// 定义单链表节点结构 BM5 合并k个已排序的链表
struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(nullptr) {}
};


bool compare(ListNode *a, ListNode *b) { return a->val > b->val; }
class Solution {
public:
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   *
   * @param lists ListNode类vector
   * @return ListNode类
   */

  ListNode *mergeKLists(std::vector<ListNode *> &lists) {
    // write code here
    //        边界处理
    if (lists.empty()) {
      return nullptr;
    }
    if (lists.size() == 1)
      return lists[0];
    //    定义虚拟头节点
    ListNode *dummy = new ListNode(-1);
    //  方法1
    //    在循环体中调用合并链表函数 时间复杂度为O(k^2N)
    //    k是链表的数量，N是每个链表的平均长度 for (auto begin = lists.begin();
    //    begin != lists.end(); ++begin){
    //        dummy->next = mergeTwoLists(dummy->next, *begin);
    //    }
    //        return dummy->next;
    //  方法2
    std::priority_queue<ListNode *, std::vector<ListNode *>, decltype(&compare)> minHeap(compare);
    //    初始化堆
    for (auto begin = lists.begin(); begin != lists.end(); ++begin) {
      if (*begin != nullptr)
        minHeap.push(*begin);
    }
    ListNode *curr = dummy;
    while (!minHeap.empty()) {
      ListNode *top = minHeap.top();
      minHeap.pop();
      curr->next = top;
      curr = curr->next;
      //     将top的next加入到堆中
      if (top->next != nullptr)
        minHeap.push(top->next);
    }
    return dummy->next;
    //  方法3
    //    return divideMerge(lists, 0, lists.size() - 1);
  }

  //    改进 使用分治思想进行合并链表 时间复杂度为O(k*Nlogk)
  ListNode *divideMerge(std::vector<ListNode *> &lists, int left, int right) {
    if (left == right)
      return lists[left];
    if (left > right)
      return nullptr;
    int mid = (left + right) / 2;
    return mergeTwoLists(divideMerge(lists, left, mid),
                         divideMerge(lists, mid + 1, right));
  }

  ListNode *mergeTwoLists(ListNode *pHead1, ListNode *pHead2) {
    // write code here
    //        边界处理
    if (pHead1 == nullptr)
      return pHead2;
    if (pHead2 == nullptr)
      return pHead1;
    ListNode *dummy = new ListNode(-1);
    ListNode *cur = dummy;
    while (pHead1 != nullptr && pHead2 != nullptr) {
      if (pHead1->val > pHead2->val) {
        cur->next = pHead2;
        pHead2 = pHead2->next;
      } else {
        cur->next = pHead1;
        pHead1 = pHead1->next;
      }
      cur = cur->next;
    }
    //        剩余的链表
    if (pHead1 != nullptr)
      cur->next = pHead1;
    else
      cur->next = pHead2;
    return dummy->next;
  }
};